<html>
<head>
 
</head>
<body style="text-align=center;font-size:32px;">
<table align="center">
<tr><td><div id="problemNum" style='background-color:#999999;width:800;text-align:center;font-size:32px;'></div></td></tr>
<tr><td><div id="problemContent" style='word-wrap:break-word;background-color:#bbbbbb;width:800;text-align:left;font-size:Npx;'></div></td></tr>
<tr><td><div id="sum" style='word-wrap:break-word; color:#ffff22;font-size:48;background-color:#8855ff;width:800;text-align:center;'></div></td></tr>
<tr><td><div id="copyleft" style='word-wrap:break-word; color:#ffff22;font-size:18;background-color:#666666;width:800;text-align:right;'></div></td></tr>
<script language="javascript">
    //---------------------------------//
    // Project Euler 
    //
    // Author:thrombin
    //   Date:2015-12-18
    //---------------------------------//  
var p_order=18;//Problem Order
 
var problem='By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.\
3<br/>\
7 4<br/>\
2 4 6<br/>\
8 5 9 3<br/>\
That is, 3 + 7 + 4 + 9 = 23.<br/>\
Find the maximum total from top to bottom of the triangle below:<br/>\
75<br/>\
95 64<br/>\
17 47 82<br/>\
18 35 87 10<br/>\
20 04 82 47 65<br/>\
19 01 23 75 03 34<br/>\
88 02 77 73 07 63 67<br/>\
99 65 04 28 06 16 70 92<br/>\
41 41 26 56 83 40 80 70 33<br/>\
41 48 72 33 47 32 37 16 94 29<br/>\
53 71 44 65 25 43 91 52 97 51 14<br/>\
70 11 33 28 77 73 17 78 39 68 17 57<br/>\
91 71 52 38 17 14 91 43 58 50 27 29 48<br/>\
63 66 04 68 89 53 67 30 73 16 69 87 40 31<br/>\
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23<br/>\
NOTE: As there are only 16384 routes, it is possible to solve this problem by trying every route. <br/>\
However, Problem 67, is the same challenge with a triangle containing one-hundred rows; it cannot be <br/>\
solved by brute force, and requires a clever method! ;o)';
 
 
//solve the problem
//==============编程思路简介================
//  采用动态规划
//  定义一个数组sum和原始数组大小相同，
//  但是sum的每一行都代表其能够到达该数字路线中的最大值
//   这样逐行得到sum数组后，最后一行中的最大值就是问题要求的
//=====================================
var problem_str='\
75 \
95 64 \
17 47 82 \
18 35 87 10 \
20 04 82 47 65 \
19 01 23 75 03 34 \
88 02 77 73 07 63 67 \
99 65 04 28 06 16 70 92 \
41 41 26 56 83 40 80 70 33 \
41 48 72 33 47 32 37 16 94 29 \
53 71 44 65 25 43 91 52 97 51 14 \
70 11 33 28 77 73 17 78 39 68 17 57 \
91 71 52 38 17 14 91 43 58 50 27 29 48 \
63 66 04 68 89 53 67 30 73 16 69 87 40 31 \
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23';
var num_triangle=new Array(15);
var sum=new Array(15);
 
//从复制得来的字符串，得到三角形数组
var problem_array=problem_str.split(' ');
for(var i=0;i<num_triangle.length;i++){
    num_triangle[i]=new Array(i+1);
    sum[i]=new Array(i+1);
    for(var j=i*(i+1)/2,k=0;j<(i+1)*(i+2)/2;j++,k++){
        num_triangle[i][k]=parseInt(problem_array[j]);
    }
}
//开始动态规划，逐行更新sum数组
sum[0][0]=num_triangle[0][0];
for(var i=1;i<num_triangle.length;i++){
    for(var j=0;j<num_triangle[i].length;j++){
        if(j==0){sum[i][j]=sum[i-1][j]+num_triangle[i][j];continue;}
        if(j==(num_triangle[i].length-1)){sum[i][j]=sum[i-1][j-1]+num_triangle[i][j];continue;}
        var tmp1=sum[i-1][j-1]+num_triangle[i][j];
        var tmp2=sum[i-1][j]+num_triangle[i][j];
        sum[i][j]=(tmp1>tmp2)?(tmp1):(tmp2);
    }
}
 
//求sum数组最后一行的最大值
var N=sum.length-1;
var max=sum[N][0];
for(var j=0;j<sum[N].length;j++){
    if(sum[N][j]>max)max=sum[N][j];
}
 
//update browser
document.getElementById("problemNum").innerHTML="Project Euler-Problem "+p_order;
document.getElementById("problemContent").innerHTML=problem;
document.getElementById("sum").innerHTML="Answer:"+max;
document.getElementById("copyleft").innerHTML="CopyLeft@Thrombin 2015";
</script>
</body>
</html>